#!/usr/bin/env python2.7

# Description of the puzzle here: https://www.spotify.com/uk/jobs/tech/catvsdog/

__author__ = "Antonis Thomas"
__email__ = "antonis.thomas@gmail.com"
__date__ = "2013-02-10"


# Original code for the maxIndySet function by prof. David Eppstein, April 2002.
# Original code obtainable at http://www.ics.uci.edu/~eppstein/PADS/
# The code was edited so that the function returns an independent set rather than a maximum matching.
#
# This function returns a maximum independent set of the input graph. 
# It is an implementation of the Hopcroft-Karp algorithm for finding a 
# maximum matching of a bipartite graph. A maximum independent set for 
# bipartite graphs is known to be obtained by a maximum matching from
# Konig's Theorem.
#
# Note that in our case the graph might have isolated nodes. Eppstein's implentation 
# adds the isolated nodes in A in the independet set but does not treat the isolated 
# nodes in B (as they are not part of the graph representation). This issue is dealt 
# with when the graph is constructed by counting the isolated nodes in B.

def maxIndySet(graph):
    
    """
    Let the input be bipartite G=(A,B,E) where A,B is two disjoint sets of vertices and E
    is the edge relation. The graph is given as a dictionary where each a in A is associated to 
    a list of its neighbors in B. The function returns a tuple (C,D) where C is a subset of A,
    D is a subset of B and C union D is a maximum independent set of G.
    """

    # initialize greedy matching (redundant, but faster than full search)
    matching = {}
    for u in graph:
        for v in graph[u]:
            if v not in matching:
                matching[v] = u
                break

    while True:
        # structure residual graph into layers
        # pred[u] gives the neighbor in the previous layer for u in U
        # preds[v] gives a list of neighbors in the previous layer for v in V
        # unmatched gives a list of unmatched vertices in final layer of V,
        # and is also used as a flag value for pred[u] when u is in the first layer
        preds = {}
        unmatched = []
        pred = {u:unmatched for u in graph}
        for v in matching:
            del pred[matching[v]]
        layer = list(pred)

        # repeatedly extend layering structure by another pair of layers
        while layer and not unmatched:
            newLayer = {}
            for u in layer:
                for v in graph[u]:
                    if v not in preds:
                        newLayer.setdefault(v,[]).append(u)
            layer = []
            for v in newLayer:
                preds[v] = newLayer[v]
                if v in matching:
                    layer.append(matching[v])
                    pred[matching[v]] = v
                else:
                    unmatched.append(v)

        # did we finish layering without finding any alternating paths?
        if not unmatched:
            unlayered = {}
            for u in graph:
                for v in graph[u]:
                    if v not in preds:
                        unlayered[v] = None
            return (list(pred),list(unlayered))

        # recursively search backward through layers to find alternating paths
        # recursion returns true if found path, false otherwise
        def recurse(v):
            if v in preds:
                L = preds[v]
                del preds[v]
                for u in L:
                    if u in pred:
                        pu = pred[u]
                        del pred[u]
                        if pu is unmatched or recurse(pu):
                            matching[v] = u
                            return True
            return False

        for v in unmatched: recurse(v)


def problemToGraph():
    """
    This turns the input to a graph structure.
    """
    
    cdv = map(int, raw_input().split())
    catL = []   # cat lovers
    dogL = []   # dog lovers
    graph = {}
    
    for i in xrange(0,cdv[2]): 
        v = raw_input().split()
        vote = [v[0], v[1]]
        
        if v[0][0] == 'C':
            catL.append(vote)
        else:
            dogL.append(vote)
    
    """
    strictly less than n^2 steps to build the graph from the input data
    votes is a list of votes that contains pairs [love, hate]
    love, hate are integer numbers represented by strings 
    
    In the graph nodes are represented by lowercase c,d 
    for cat/dog lover and a identifier number (starting at 0) 
    """ 
    
    # dogLConnected is used to count how many vertices of the
    # graph that correspond to Dog Lovers are isolated. This treats 
    # an issue with the implementation of the max indy set function 
    # and discussed in the comments there.
    dogLConnected = []
    for i,c in enumerate(catL):
        cn = [] #neighbors of c are kept here
        for j,d in enumerate(dogL):
            if c[0] == d[1] or c[1] == d[0]:
                cn.append('d'+str(j))
                dogLConnected.append(j)
        graph['c'+str(i)] = cn
    
    #below we put dogLConnected in set so it loses duplicates 
    isolatedDogL = len(dogL)-len(set(dogLConnected))
    
    
    return graph, isolatedDogL


if __name__ == "__main__":
    problems = int(raw_input())
    for prob in xrange(0, problems):
        graph, isolatedDogL = problemToGraph()
        (c,d) = maxIndySet(graph)
        print len(c)+len(d)+isolatedDogL
